package leecode.链表;

/**
 * description:
 * author: wangxi
 * date:  2022/5/7 12:13 上午
 *
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 **/
public class RemoveNthFromEnd {

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    /**
     *  双指针法，不需要2次遍历
     *  由于我们需要找到倒数第 n个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，
     *  并且 first 比 second 超前 nn 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n个节点。
     *
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0) {
            return head;
        }
        // 定义一个哑元节点，防止第一个节点被删除
        ListNode first = new ListNode(-1);
        first.next = head;
        ListNode cur1 = first;
        ListNode cur2 = first;
        for (int i = 0; i < n; i++) {
            cur1 = cur1.next;
        }
        while (cur1 != null && cur1.next != null) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        cur2.next = cur2.next.next;
        return first.next;
    }
}
